//
// intelligentSnake.c
// Created by Yuxuan Liao on 12/27/2020
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
#include <termios.h>

#define WALL '*'
#define FOOD '$'
#define BLANK ' '

#define BODY 'X'
#define HEAD 'H'
#define SNAKE_HEAD ((snakeLength)-1)
#define GAME_OVER "GAME OVER!\n"
#define STATUS_NORMAL 0
#define STATUS_GAME_OVER 1

#define WIDTH 50
#define HEIGHT 25
#define SNAKE_MAX_LENGTH ((WIDTH - 2) * (HEIGHT - 2))

#define UP 0, -1
#define DOWN 0, 1
#define LEFT -1, 0
#define RIGHT 1, 0

#define FOOD_PROBABILITY 0.1
#define FOOD_MAX_NUMBER (SNAKE_MAX_LENGTH / 6)
#define bool int
#define true 1
#define false 0

// initialize the map with WALL and BLANK
void initializeMap(int width, int height);

//  Check out if the snake can make its move
bool predictMovable(int dx, int dy);

// move the snake one step by dx and dy
void snakeMove(int dx, int dy);

// Randomly place food at a blank place
void placeFood(double food_prob);

// check if the snake can eat food
bool eatFood(int dx, int dy);

// clear the screen
void clearScreen();

// clear the snake
void clearSnake();

// draw the sanke on the map
void drawSnake();

// draw the food on the map
void drawFood();

// Clear the screen and print out the map.
void printMap();

/* 
    Read in only one character and discard the following characters.
    If no character is read, return space character. 
*/
char readInput();

// check if the game is over
int isGameOver();

// Caculate and make intelligent snake move
char nextMove();

// get distance by |x1 - x2| + |y1 - y2|
int getDistance(int x1, int y1, int x2, int y2);

char map[HEIGHT][WIDTH] = {0};

int snakeCol[SNAKE_MAX_LENGTH] = {1, 2, 3, 4, 5};
int snakeRow[SNAKE_MAX_LENGTH] = {1, 1, 1, 1, 1};

int foodCol[FOOD_MAX_NUMBER] = {0};
int foodRow[FOOD_MAX_NUMBER] = {0};
int foodNumber = 0;
int snakeLength = 5;
int gameStatus = STATUS_NORMAL;

unsigned long beginTime;
static struct termios ori_attr, cur_attr;

// kbhit
static __inline int tty_reset()
{
    if (tcsetattr(STDIN_FILENO, TCSANOW, &ori_attr) != 0)
        return -1;

    return 0;
}

static __inline int tty_set()
{

    if (tcgetattr(STDIN_FILENO, &ori_attr))
        return -1;

    memcpy(&cur_attr, &ori_attr, sizeof(cur_attr));
    cur_attr.c_lflag &= ~ICANON;
    cur_attr.c_lflag &= ~ECHO;
    cur_attr.c_cc[VMIN] = 1;
    cur_attr.c_cc[VTIME] = 0;

    if (tcsetattr(STDIN_FILENO, TCSANOW, &cur_attr) != 0)
        return -1;

    return 0;
}

static __inline int kbhit()
{
    fd_set rfds;
    struct timeval tv;
    int retval;

    /* Watch stdin (fd 0) to see when it has input. */
    FD_ZERO(&rfds);
    FD_SET(0, &rfds);
    /* Wait up to five seconds. */
    tv.tv_sec = 0;
    tv.tv_usec = 0;

    retval = select(1, &rfds, NULL, NULL, &tv);
    /* Don't rely on the value of tv now! */

    if (retval == -1)
    {
        perror("select()");
        return 0;
    }
    else if (retval)
        return true;
    /* FD_ISSET(0, &rfds) will be true. */
    else
        return 0;
    return 0;
}

int main()
{
    int tty_set_flag;
    tty_set_flag = tty_set();
    srand(time(NULL));
    initializeMap(WIDTH, HEIGHT);
    drawSnake();
    printMap();
    int ch = 'D';
    while (!isGameOver())
    {
        usleep(150000);
        char tmp_ch = nextMove();
        if (!(tmp_ch == 'W' && ch == 'S') && !(tmp_ch == 'S' && ch == 'W') && !(tmp_ch == 'A' && ch == 'D') && !(tmp_ch == 'D' && ch == 'A') && (tmp_ch == 'W' || tmp_ch == 'A' || tmp_ch == 'S' || tmp_ch == 'D'))
            ch = tmp_ch;
        switch (ch)
        {
        case 'W':
            snakeMove(UP);
            break;
        case 'A':
            snakeMove(LEFT);
            break;
        case 'S':
            snakeMove(DOWN);
            break;
        case 'D':
            snakeMove(RIGHT);
            break;
        default:
            break;
        }

        placeFood(FOOD_PROBABILITY);
        printMap();
    }
    clearScreen();
    printf(GAME_OVER);

    if (tty_set_flag == 0)
        tty_reset();
    return 0;
}

// initialize the map with WALL and BLANK
void initializeMap(int width, int height)
{
    beginTime = time(NULL);
    for (int row = 0; row < height; ++row)
    {
        for (int col = 0; col < width; ++col)
        {
            if (row == 0 || row == height - 1 || col == 0 || col == width - 1)
            {
                map[row][col] = WALL;
            }
            else
            {
                map[row][col] = BLANK;
            }
        }
    }
}

// clear the screen
void clearScreen()
{
    // system("clear");
    printf("\x1b[H\x1b[2J");
}

// Clear the screen and print out the map.
void printMap()
{
    clearScreen();
    for (int row = 0; row < HEIGHT; ++row)
    {
        for (int col = 0; col < WIDTH; ++col)
        {
            putchar(map[row][col]);
        }
        putchar('\n');
    }
}

/* 
Read in only one character and discard the following characters.
If no character is read, return space character. 
*/
char readInput()
{
    char ch;
    if (scanf("%c", &ch))
    {
        while (getchar() != '\n')
            continue;
        return ch;
    }
    else
    {
        return ' ';
    }
}

// Randomly place food at a blank place
void placeFood(double food_prob)
{
    int x, y;
    if (foodNumber + 1 > FOOD_MAX_NUMBER)
        return;
    if ((double)rand() / RAND_MAX > food_prob)
        return;

    do
    {
        x = (int)(WIDTH * ((double)rand() / RAND_MAX));
        y = (int)(HEIGHT * ((double)rand() / RAND_MAX));
    } while (map[y][x] != BLANK);

    foodNumber++;
    foodCol[foodNumber - 1] = x;
    foodRow[foodNumber - 1] = y;
    drawFood();
}

// check if the snake can eat food
bool eatFood(int dx, int dy)
{
    int headX = snakeCol[SNAKE_HEAD] + dx;
    int headY = snakeRow[SNAKE_HEAD] + dy;

    if (map[headY][headX] == FOOD)
    {
        if (snakeLength + 1 > SNAKE_MAX_LENGTH)
            return false;

        snakeLength++;
        snakeCol[SNAKE_HEAD] = headX;
        snakeRow[SNAKE_HEAD] = headY;

        foodNumber--;
        for (int body = 0; body < foodNumber; ++body)
        {
            if (headX == foodCol[body] && headY == foodRow[body])
            {
                foodCol[body] = foodCol[foodNumber];
                foodRow[body] = foodRow[foodNumber];
                break;
            }
        }
        return true;
    }
    return false;
}

//  Check out if the snake can make its move
bool predictMovable(int dx, int dy)
{

    int headX = snakeCol[SNAKE_HEAD] + dx;
    int headY = snakeRow[SNAKE_HEAD] + dy;

    // check if out of the map
    if (headX <= 0 || headX >= WIDTH - 1 || headY <= 0 || headY >= HEIGHT - 1)
    {
        return false;
    }
    // check if hit the wall
    if (map[headY][headX] == WALL)
    {
        return false;
    }

    // check if hits itself
    for (int body = 0; body < snakeLength; ++body)
    {
        int bodyX = snakeCol[body];
        int bodyY = snakeRow[body];

        if (headX == bodyX && headY == bodyY)
        {
            return false;
        }
    }

    return true;
}

// get distance by |x1 - x2| + |y1 - y2|
int getDistance(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}

// Caculate and make intelligent snake move
char nextMove()
{
    int headX = snakeCol[SNAKE_HEAD];
    int headY = snakeRow[SNAKE_HEAD];
    int distMin = 9999;
    char direction = 'D';
    for (int i = 0; i < foodNumber; ++i)
    {
        int fX = foodCol[i];
        int fY = foodRow[i];
        int dist = 0;
        if (predictMovable(UP))
        {
            dist = getDistance(headX, headY - 1, fX, fY);
            if (dist < distMin)
            {
                distMin = dist;
                direction = 'W';
            }
        }

        if (predictMovable(DOWN))
        {
            dist = getDistance(headX, headY + 1, fX, fY);
            if (dist < distMin)
            {
                distMin = dist;
                direction = 'S';
            }
        }

        if (predictMovable(LEFT))
        {
            dist = getDistance(headX - 1, headY, fX, fY);
            if (dist < distMin)
            {
                distMin = dist;
                direction = 'A';
            }
        }

        if (predictMovable(RIGHT))
        {
            dist = getDistance(headX + 1, headY, fX, fY);
            if (dist < distMin)
            {
                distMin = dist;
                direction = 'D';
            }
        }
    }

    if (distMin == 9999)
    {
        if (predictMovable(RIGHT))
            direction = 'D';
        if (predictMovable(LEFT))
            direction = 'A';
        if (predictMovable(UP))
            direction = 'W';
        if (predictMovable(DOWN))
            direction = 'S';
    }

    return direction;
}

// clear the snake
void clearSnake()
{
    for (int body = 0; body < snakeLength; ++body)
    {
        map[snakeRow[body]][snakeCol[body]] = BLANK;
    }
}

// draw the food on the map
void drawFood()
{
    for (int i = 0; i < foodNumber; ++i)
    {
        map[foodRow[i]][foodCol[i]] = FOOD;
    }
}

// draw the snake on the map
void drawSnake()
{
    for (int body = 0; body < snakeLength; ++body)
    {
        map[snakeRow[body]][snakeCol[body]] = ((SNAKE_HEAD) == body) ? HEAD : BODY;
    }
}

// move the snake one step by dx and dy
void snakeMove(int dx, int dy)
{
    if (!predictMovable(dx, dy))
    {
        gameStatus = STATUS_GAME_OVER;
        return;
    }
    clearSnake();
    if (!eatFood(dx, dy))
    {
        for (int body = 0; body < SNAKE_HEAD; ++body)
        {
            snakeCol[body] = snakeCol[body + 1];
            snakeRow[body] = snakeRow[body + 1];
        }
        snakeCol[SNAKE_HEAD] = snakeCol[SNAKE_HEAD] + dx;
        snakeRow[SNAKE_HEAD] = snakeRow[SNAKE_HEAD] + dy;
    }
    drawSnake();
}

// check if the game is over
bool isGameOver()
{
    return gameStatus == STATUS_GAME_OVER;
}
